import java.util.Arrays;

public class Solution931 {
    public int minFallingPathSum(int[][] matrix) {
        int[] f=new int[matrix[0].length];
        for (int i=0;i<matrix[0].length;i++){
            f[i]=matrix[0][i];
        }
        for (int i=1;i<matrix.length;i++){
            int[] g=new int[matrix[0].length];
            for (int j=0;j<matrix[0].length;j++){
                g[j]=f[j]+matrix[i][j];
                if (j!=0){
                    g[j]=Math.min(g[j],f[j-1]+matrix[i][j]);
                }
                if (j!=matrix[0].length-1){
                    g[j]=Math.min(g[j],f[j+1]+matrix[i][j]);
                }
            }
            f=g;
        }
        return Arrays.stream(f).min().getAsInt();
    }

    public static void main(String[] args) {
        System.out.println(new Solution931().minFallingPathSum(new int[][]{{2,1,3},{6,5,4},{7,8,9}}));
    }
}
